/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

/**
 * 
 */
package org.apache.wikimark;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;

class Distribution implements Iterable<Integer> {    	
	private static Random rnd = new Random();
	
	private final int[] values;
	private final int[] bounds;
	final int total;
	final int[][] density;
	
	Distribution(final int[][] density, int mult) {
		this.density = density;
		values = new int[density.length];
		bounds = new int[density.length];
		int sum = 0;
		for (int i = 0; i < density.length; i++) {
			values[i] = density[i][0];
			sum += density[i][1] * mult;
			bounds[i] = sum;
		}
		total = sum;
	}


	public Iterator<Integer> iterator() {
		return new Iterator<Integer>() {
			
	    	Set<Integer> inUse = new HashSet<Integer>(total); 

			public boolean hasNext() {
				return inUse.size() < total;
			}

			public Integer next() {
				if (!hasNext()) {
					throw new NoSuchElementException();
				}
				int uniform;
				do {
					uniform = rnd.nextInt(total);
				} while (inUse.contains(uniform));
				inUse.add(uniform);
				final int pos = Arrays.binarySearch(bounds, uniform);
				final int nonUniform = pos >= 0 ? pos :  -pos - 1;
				return values[nonUniform];
			}

			public void remove() {
				throw new UnsupportedOperationException();
			}
		};
	}
}